Autonomous navigation of a vehicle requires certainty in the position of the vehicle with a sufficient degree of accuracy. Calculating a precise physical position for the vehicle in respect to a representation of its surroundings can be referred to as localization. Localization can be performed for autonomous vehicles by comparing a representation of the current position of the vehicle in respect to a road or other geographic features to a representation of the same road or features recorded on a detailed virtual map.